#pragma once

#include <iostream>
#include <cuda_runtime.h>

static __device__ __host__ __uint128_t choose(int n, int k)
{
   if (n < k)
   {
      return 0; // special case
   }
   
   if (n == k || k==0)
      return 1;

   int delta, iMax;
   
   if (k < n - k) // ex: choose(100,3)
   {
      delta = n - k;
      iMax = k;
   }
   else // ex: choose(100,97)
   {
      delta = k;
      iMax = n - k;
   }
   // delta = 97, iMax = 3

   __uint128_t ans = delta + 1; // ans = 98

   for (int i = 2; i <= iMax; ++i) // i=2, 3
   {
      ans = (ans * (delta + i)) / i;
   }

   return ans;
}

// return largest v where v < a and vCb < x
static __device__ __host__ unsigned char largestV(unsigned char a, unsigned char b, __uint128_t x)
{
   unsigned char v = a - 1;
   while (choose(v, b) > x)
   {
      --v;
   }
   return v;
}

// return the mth combination of n choose k
static __device__ __host__ void mThComb(__uint128_t m, __uint128_t total, unsigned char n, unsigned char k, unsigned char *data)
{
   unsigned char a = n;
   unsigned char b = k;
   __uint128_t x = total - 1 - m; // the "dual" of mth combination

   for (unsigned char i = 0; i < k; ++i)
   {
      data[i] = largestV(a, b, x); // largest value v, where v<a and vCb <x
      x = x - choose(data[i], b);
      a = data[i];
      b = b - 1;
   }

   // generating elements
   for (unsigned char i = 0; i < k; ++i)
   {
      data[i] = n - 1 - data[i];
   }
}